home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / LANG / GOFER / scripts / recur < prev    next >
Text File  |  1993-11-25  |  1KB  |  45 lines
  1. -- Fibonacci series modulo p                    GCW  10/11/92
  2.  
  3. -- recur n takes the prefix of an infinite list up to the point where
  4. -- the first n items reoccur. This might not terminate!
  5.  
  6. recur :: Eq [a] => Int -> [a] -> [a]
  7.  
  8. -- recur n has to be defined on lists of items in an equality type, else 
  9. -- how can we test for recurrence?
  10.  
  11. recur n xs = ms ++ f (drop (length ms) xs) ms where
  12.              ms                                   = take n xs
  13.              f (ys@(u:us)) zs | zs == take n ys   = []
  14.                               | otherwise         = u:f us zs
  15.  
  16. -- NB. drop n drops n items from head of a list. take n drops all
  17. -- the rest. The auxiliary function f is defined so that f xs ms is
  18. -- the largest prefix of xs whose removal leaves a list with ms as 
  19. -- a prefix. ys@(u:us) means that the list ys has the form u:us.
  20.  
  21. -- The Lucas sequence starting with a,b.
  22. lucas :: Int -> Int -> [Int]
  23. lucas a b = a:lucas b (a+b)
  24.  
  25. -- The Fibonacci sequence.
  26. fibs :: [Int]
  27. fibs = lucas 0 1
  28.  
  29. -- what is cycle length of Fibonacci numbers modulo p ?
  30. -- named after C.T.C.Wall.
  31. wall :: Int -> Int
  32. wall p = length (recur 2 [ x `mod` p | x <- fibs ])
  33.  
  34. -- [ wall n | n <- [2, 3, 5, 7, 11, 13] ] gives the values
  35. -- [3, 8, 20, 16, 10, 28] 
  36.  
  37. length :: [a] -> Int
  38. length x = sum [ 1 | _ <- x ]
  39.  
  40. drop :: Int -> [a] -> [a]
  41. drop 0 xs         = xs
  42. drop _ []         = []
  43. drop (n+1) (x:xs) = drop n xs
  44.  
  45.